package changjietong;

import java.util.*;
import java.util.function.BiConsumer;
import java.util.stream.Collectors;

public class UniquePermutations {
    
    public static void main(String[] args) {
        // 包含0到9的数字数组
        int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        // 存储最终结果的列表
        List<List<Integer>> results = new ArrayList<>();
        
        // 用于跟踪哪些数字已被使用的布尔数组
        boolean[] used = new boolean[10];
        
        // 开始回溯生成排列
        backtrack(digits, used, new ArrayList<>(), results);
        
        // 打印所有生成的排列
        for (List<Integer> permutation : results) {
            System.out.println(permutation);
        }
    }
    
    /**
     * 回溯方法生成所有唯一的4位排列。
     * 
     * @param digits  用于排列的数字数组
     * @param used    跟踪数字是否已被使用的布尔数组
     * @param current 当前构建的排列
     * @param results 存储所有排列的列表
     */
    private static void backtrack(int[] digits, boolean[] used, List<Integer> current, List<List<Integer>> results) {
        // 基本情况：如果当前排列有4个数字，添加到结果中
        if (current.size() == 4) {
            results.add(new ArrayList<>(current));
            return;
        }
        
        // 遍历每个数字生成排列
        for (int i = 0; i < digits.length; i++) {
            // 跳过已经在当前排列中使用过的数字
            if (used[i]) continue;
            
            // 选择当前数字
            used[i] = true;
            current.add(digits[i]);
            
            // 递归构建排列
            backtrack(digits, used, current, results);
            
            // 回溯：移除最后添加的数字，并将其标记为未使用
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}
